from typing import List
from functools import lru_cache
count = 1
numCalls = 0

"""
背包问题就是拿和不拿的问题。

也没有办法用贪心算法做

思路：

不拿这个 和 拿这个  比较
"""
def knapsack(w: List[int], v: List[int], index: int, c: int):
    """w为物品重量，v为物品价值，c为背包的容量
    """
    @lru_cache(None)
    def helper(index, c):
        global count
        if index < 0 or c <=0:
            return 0
        count += 1
        # print(index, c)
        # 不拿这个，去考虑下一个
        res = helper(index-1, c)
        # 有剩余空间
        if c >= w[index]:
            # 另一种策略是 v[index]  + knapsack(w, v, index-1, c-w[index])
            res = max(res, v[index] + helper(index-1, c-w[index]))
        return res
    return helper(index, c)

def maxVal(w, v, i, aW):
    """
    :param w: 重量
    :param v: 价值
    :param i: 物品的种类-1
    :param aW: 剩余重量
    :return:
    """
    global numCalls
    numCalls += 1
    if i == 0:
        if w[i] <= aW:  # 如果i的重量小于剩余的重量
            return v[i]  # 放进去
        else:
            return 0  # 不放进去
    without_i = maxVal(w, v, i - 1, aW)
    if w[i] <= aW:
        with_i = v[i] + maxVal(w, v, i - 1, aW - w[i])
    else:
        return without_i
    return max(with_i, without_i)

def test():
    pass

if __name__ == "__main__":
    w = [0, 2, 2, 6, 5, 4, 100]
    v = [0, 6, 3, 5, 4, 6, 100]
    print(knapsack(w, v, len(w)-1, 10))
    print("count=", count)


